// https://www.lintcode.com/problem/count-primes/

public class Solution {
    /**
     * @param n: a integer
     * @return: return a integer
     */
    public int countPrimes(int n) {
        // write your code here
        int ret = 0;
        int[] nums = new int[n];
        Arrays.fill(nums, 0);
        for (int i = 2; i < (int)Math.sqrt(n) + 1; ++i) {
            if (nums[i] == 0) {
                for (int j = 2; (i * j) < n; ++j) {
                    nums[i * j] = 1;
                }
            }
        }
        for (int i = 2; i < n; ++i) {
            if (nums[i] == 0) {
                ret += 1;
            }
        }
        return ret;
    }
}